#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct{
    int weight;
    int parent;
    int lchild;
    int rchild;
}HTNode, *HuffmanTree;

typedef char **HuffmanCode; //编码表

//在HT[1...n]选择parent为0且weight最小的两个节点，其下标分别为index1、index2
void select(HuffmanTree HT, int n, int &index1, int &index2){
    index1 = index2 = 0;
    for(int i = 1; i <= n; i++){
        if(HT[i].parent == 0){
            if(index1 == 0)
                index1 = i;
            else if(HT[i].weight < HT[index1].weight)
                index1 = i;
        }
    }

    for(int i = 1; i <= n; i++){
        if(HT[i].parent == 0 && i != index1){
            if(index2 == 0)
                index2 = i;
            else if(HT[i].weight < HT[index2].weight)
                index2 = i;
        }
    }  
    // printf("\n%d - %d\n", index1, index2);
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
    if(n <= 1)  return;
    //哈弗曼树中节点的个数（只存在度为0和2的， n2 = n0 + 1）
    int m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));//0号单元不使用
    //初始化
    int i = 1;
    HuffmanTree p = HT + 1;
    for(; i <= n; i++, p++, w++){
        *p = {*w, 0, 0, 0};
    }
    // for(int i = 1; i <= n; i ++){
    //     printf("%d\t", HT[i].weight);
    // }
    // printf("\n");

    for(; i <= m; i++, p++)
        *p = {0, 0, 0, 0};
    
    //构建哈夫曼树
    int index1, index2;
    for(i = n + 1; i <= m; i++){
        select(HT, i - 1, index1, index2);
        HT[index1].parent = i;
        HT[index2].parent = i;
        HT[i].lchild = index1;
        HT[i].rchild = index2;
        HT[i].weight = HT[index1].weight + HT[index2].weight;
    }
    // printf("\n");
    // for(int i = 1; i <= m ; i++){
    //     if(HT[i].lchild || HT[i].rchild){
    //         printf("%d:", i);
    //         if(HT[i].lchild){
    //             printf("%d", HT[i].lchild);
    //         }
    //         if(HT[i].rchild){
    //             printf("-%d", HT[i].rchild);
    //         }
    //     }
    //     printf("\n");
    // }
    // printf("\n");
    
    //从叶子到根逆向求每个字符的赫夫曼编码
    HC = (HuffmanCode) malloc((n + 1) * sizeof(char *));
    char *cd = (char *) malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    for(int i = 1; i <= n; i++){  
        int start = n - 1;
        int c = i;
        int f = HT[i].parent;
        for(; f != 0; c = f, f = HT[f].parent){
            if(HT[f].lchild == c)   cd[--start] = '0';
            else cd[--start] = '1';
        }
        HC[i] = (char *) malloc((n - start) * sizeof(char));
        strcpy(HC[i], cd + start);
    }
    //释放工作空间
    free(cd);
}